package day1_array.leetcode;

/**
 * @author yuisama
 * @date 2023年07月07日 16:04
 * @description
 * 二分查找定位左右区间问题
 */
public class Num34_SearchRange {
    public int[] searchRange(int[] nums, int target) {
        if (nums.length == 0) {
            return new int[] {-1,-1};
        }
        int l = leftRange(nums,target);
        int r = rightRange(nums,target);
        return new int[] {l,r};
    }
    // 在有序数组nums中，找到第一个目标值为target的元素下标
    public int leftRange(int[] nums,int target) {
        if (nums.length == 0) {
            return -1;
        }
        int l = 0,r = nums.length - 1;
        while (l <= r) {
            int mid = l + ((r - l) >> 1);
            if (target < nums[mid]) {
                r = mid - 1;
            }else if (target > nums[mid]) {
                l = mid + 1;
            }else {
                // 当nums[mid] == target时，说明小于target的元素位于[l..mid - 1]区间
                // 因此，缩小r的范围
               r = mid - 1;
            }
        }
        // 循环退出时，r落在首个小于target的元素，l恰好落在第一个target的元素
        // 若l == nums.length或nums[l] != target，说明nums中不存在目标值
        if (l == nums.length || nums[l] != target) {
            return -1;
        }
        return l;
    }
    // 在有序数组nums中，找到最后一个目标值为target的索引
    public int rightRange(int[] nums,int target) {
        if (nums.length == 0) {
            return -1;
        }
        int l = 0,r = nums.length - 1;
        while (l <= r) {
            int mid = l + ((r - l) >> 1);
            if (target < nums[mid]) {
                r = mid - 1;
            }else if (target > nums[mid]) {
                l = mid + 1;
            }else {
                // 当nums[mid] == target时，说明大于target的元素位于[mid + 1..r]区间
                // 因此，增大l的范围
                l = mid + 1;
            }
        }
        // 循环退出时，l落在首个大于target的元素，r恰好落在最后一个target的元素
        // 若r < 0或nums[r] != target，说明nums中不存在目标值
        if (r < 0 || nums[r] != target) {
            return -1;
        }
        return r;
    }
}

